package com.leetcodehot.problems;

import java.util.ArrayDeque;
import java.util.Deque;

public class problems862 {


    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length, ans = n + 1;
        long[] s = new long[n + 1];
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] + nums[i]; // 计算前缀和
        Deque<Integer> q = new ArrayDeque<Integer>();
        for (int i = 0; i <= n; ++i) {
            long curS = s[i];
            while (!q.isEmpty() && curS - s[q.peekFirst()] >= k)
                ans = Math.min(ans, i - q.pollFirst()); // 优化一，记录当前，要i-左尽可能小，所以这一轮之后j肯定不要了
            while (!q.isEmpty() && s[q.peekLast()] >= curS)
                q.pollLast(); // 优化二，升序队列
            q.addLast(i);
        }
        return ans > n ? -1 : ans;
    }


}
